<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>Insertion Sort</title>
  <meta
 content="Algorithms - Insertion Sort"
 name="description" />
  <meta
 content="Algorithms - Insertion Sort"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right">
<a href="../gif.html">Gif</a> 
| <a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
| <a href="../OnHTML5.html">HTML5</a>
| <a href="../News/NewsMain.html">News</a>
| <a href="../cplusplus/cpptut.html">C++</a>
| <a href="../Java/tutorial/on_java.html">Java</a>
| <a href="../php/phptut.html">PHP</a>
| <a href="../DesignPatterns/introduction.html">Design Patterns</a>
</div>
</div>

<div id="contenttext">

<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>

<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>
<br />
<br />
<br />
<br />

<div style="padding: 10px;"><span class="titletext">Algorithms<br />
- Insertion Sort
</span></div>
<br /><br />
<img src="images/dijkstra_pic.jpg" alt="dijkstra"/>      
<img src="images/kandinsky.jpg" alt="kandinsky"/>      
<img src="images/knuth_pic.jpg" alt="knuth"/> 
<br /><br />
<br />
<br />

<div class="bodytext" style="padding: 12px;" align="justify">
<div class="subtitle" id="bubblesort">Insertion Sort</div>
<p>C++ code</p>
<pre>
#include &lt;iostream&gt;
#include &lt;iomanip&gt;

using namespace std;

void insert(int a[], int pos, int value) 
{
	int i = pos - 1;
	while(i >= 0 && a[i] > value) {
		a[i+1] = a[i];
		i--;
	}
	a[i+1] = value;
}
 
void sort(int a[], int size)
{
	for(int i = 1;i < size;i++) {
		insert(a,i,a[i]);
		for (int k = 0; k < size; k++) {
			cout << setw(3) << a[k] ;
		}
		cout << endl;
	}
}

int main()
{
	int a[]={15,9,8,1,4,11,7,12,13,6,5,3,16,2,10,14};
	const size_t sz = sizeof(a)/sizeof(a[0]);
	for (int i = 0; i < sz ; i++) {
		cout << setw(3) << a[i];
	}
	cout << endl;
	sort(a,sz);
	cout << endl;
}
</pre>
<br />
<p>Output from the run:</p>
<pre>
 15  9  8  1  4 11  7 12 13  6  5  3 16  2 10 14 <br/>
  9 <font color="red">15</font>  8  1  4 11  7 12 13  6  5  3 16  2 10 14 <br/>
  8  <font color="red">9 15</font>  1  4 11  7 12 13  6  5  3 16  2 10 14 <br/>
  1  <font color="red">8  9 15</font>  4 11  7 12 13  6  5  3 16  2 10 14 <br/>
  1  4  <font color="red">8  9 15</font> 11  7 12 13  6  5  3 16  2 10 14 <br/>
  1  4  8  9 11 <font color="red">15</font>  7 12 13  6  5  3 16  2 10 14 <br/>
  1  4  7  <font color="red">8  9 11 15</font> 12 13  6  5  3 16  2 10 14 <br/>
  1  4  7  8  9 11 12 <font color="red">15</font> 13  6  5  3 16  2 10 14 <br/>
  1  4  7  8  9 11 12 13 <font color="red">15</font>  6  5  3 16  2 10 14 <br/>
  1  4  6  <font color="red">7  8  9 11 12 13 15</font>  5  3 16  2 10 14 <br/>
  1  4  5  <font color="red">6  7  8  9 11 12 13 15</font>  3 16  2 10 14 <br/>
  1  3 <font color="red"> 4  5  6  7  8  9 11 12 13 15</font> 16  2 10 14 <br/>
  1  3  4  5  6  7  8  9 11 12 13 15 16  2 10 14 <br/>
  1  2  <font color="red">3  4  5  6  7  8  9 11 12 13 15 16</font> 10 14 <br/>
  1  2  3  4  5  6  7  8  9 10 <font color="red">11 12 13 15 16</font> 14 <br/>
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 <font color="red">15 16</font> <br/>
</pre>
<br /><br />
<br /><br />
<br /><br />
<br /><br />
<img src="images/song.jpg" alt="song"/> 
<div id="rightpanel">
<div align="center">
</div></div>

<br /><br />
<br /><br />



<script type="text/javascript"><!--
google_ad_client = "pub-5767010733052716";
/* 300x250, created 7/22/10 */
google_ad_slot = "4543448457";
google_ad_width = 300;
google_ad_height = 250;
//-->
</script>
<script type="text/javascript"
src="http://pagead2.googlesyndication.com/pagead/show_ads.js">
</script>
<br />


<br />
<br />
<br />


</div>
</div>
<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2010 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a>
</div>
</div>
</div>
</body>
</html>
